Лемма о подпространстве решений

Общее решение рекуррентного соотношения $f(n) = a_1f(n-1) + \dots + a_k f(n-k)$ с коэффициентами из $\mathbb{R}$ является $k$-мерным подпространством в $\mathbb{R}^{\infty}$.

Пусть $S$ — общее решение. Сначала докажем, что $S$ является подпространством. Подмножество линейного пространства является подпространством тогда и только тогда, когда оно замкнуто относительно операций сложения и умножения на скаляр. Пусть $f_1(n), f_2(n)$ — решения, $\alpha \in \mathbb{R}$, тогда: $f_1(n) + f_2(n) = a_1(f_1(n-1) + f_2(n-1)) + \dots + a_k(f_1(n-k) + f_2(n-k))$, следовательно $f_1(n) + f_2(n)$ — решение. $\alpha f_1(n) = a_1(\alpha f_1(n-1)) + \dots + a_k(\alpha f_1(n-k))$, следовательно $\alpha f_1(n)$ — решение. Таким образом, $S$ — подпространство. Теперь докажем, что $\dim(S) = k$. Рассмотрим решения $e_i(n)$ с начальными условиями $e_i(j) = [i=j]$ для $i, j = 0, \dots, k-1$. Множество $\{e_i(n)\}_{i=0}^{k-1}$ линейно независимо, так как матрица, составленная из начальных отрезков этих последовательностей, имеет ранг $k$: $$ \begin{matrix} e_0 = (1, & 0, & \dots, & 0, & e_0(k), & e_0(k+1), & \dots) \\ e_1 = (0, & 1, & \dots, & 0, & e_1(k), & e_1(k+1), & \dots) \\ \vdots \\ e_{k-1} = (0, & 0, & \dots, & 1, & e_{k-1}(k), & e_{k-1}(k+1), & \dots) \end{matrix} $$ Для любого решения $f(n)$ справедливо $f(n) = f(0)e_0(n) + f(1)e_1(n) + \dots + f(k-1)e_{k-1}(n)$. Следовательно, $\{e_i(n)\}_{i=0}^{k-1}$ — базис $S$, а значит $\dim(S) = k$. $\square$